/*
 * @author: ZJX
 * @date:   2020/04/23
 */


#include "iostream"
#include "cstdio"
#include "map"
#include "queue"
#include "vector"
#include "string.h"
#include "cstdlib"
#include "algorithm"
#include "set"
#include "ctime"
#include "cmath"

#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif

using namespace std;
typedef long long LL;
typedef unsigned char uc;

class Prime
{
public:
    bool isPrime(BigInteger a);
    BigInteger Random(int length);
    BigInteger generateSingle(int length) ;
private:

};
BigInteger Prime::Random(int length)
{
    BigInteger a = BigInteger(65537);
    BigInteger b;
    length/=5;
    for (int i = 1;i<=length;i++)
    {
        b = rand()%1000000;
        a*=b;
    }
    return a;
}
bool Prime::isPrime(BigInteger big)
{
    BigInteger dupliBigInteger = big - numOne;
    int s = 0;
    int securePara = 30;
    bool ToContinue = true;
    while (ToContinue) {
        if (dupliBigInteger&1 == 1)
        {
            ToContinue = false;
        } else {
            s++;
            dupliBigInteger = dupliBigInteger/=numTwo;
        }
    } 
    BigInteger t = dupliBigInteger;
    BigInteger b = Random(5);
    BigInteger nSubtractOne = big - numOne;
    b = (b%(big-numThree)+numTwo);
    for (int i = 0; i < securePara; i++) {
        b = b.modPow(t, big);
        if (b==numOne || b==nSubtractOne) {
            b = Random(15);
            b = (b%(big-numThree)+numTwo);
        } 
        else 
        {
            bool ok = true;
            int cnt = 0;
            while (cnt < s) {
                b = b.modPow(numTwo, big);
                cnt++;
                if (b==nSubtractOne) {
                    b = Random(15);
                    b = (b%(big-numThree)+numTwo);
                    ok = false;
                    break;
                }
            } 
            if (ok)
            {
                return false;
            }

        }
    }
    return true;
}
BigInteger Prime::generateSingle(int length) {

    BigInteger big = Random(length);

    if (!((big&1) == 1))
    {
        big = big+numOne;
    }
    while (!(*this).isPrime(big)) {
        big = Random(length);
        if (!((big&1) == 1))
        {
            big = big+numOne;
        }
    }
    return big;
}
